class TreeNode {
    val: number = 0
    left:TreeNode|null = null
    right:TreeNode|null = null

    constructor(val: number, left?:TreeNode|null,right?:TreeNode|null) {
        this.val = val;
        this.left = left===undefined ? null : left;
        this.right = right===undefined ? null : right;;
    }

    /**
     * 解法一 递归
     */
    function isValidBST(root: TreeNode | null): boolean{
        //小知识Number.MIN_VALUE 是指无限接近0，而不是负值
        return isValidBST2(root,-Number.MAX_VALUE,Number.MAX_VALUE)
    }
    
    function isValidBST2(root: TreeNode | null,min:number,max:number): boolean {
        if(root===null){
            return true
        }
    
        if(root.val >= max || root.val<=min){
            //设定界限
            return false
        }
    
        return isValidBST2(root.left,min,root.val) && isValidBST2(root.right,root.val,max);
    }

    /**
     * 解法二 中序遍历
     * 这种全局变量的解法有问题，leetcode是循环调用方法，所以全局变量的值对后续的执行会有干扰
     */
    
    let prev : TreeNode|null=null // 设定全局变量
    function isValidBST3(root: TreeNode | null): boolean{
        if(root===null){
            return true
        }
        console.log(`#${prev?.val}`)
        //查左子节点
        if(!isValidBST3(root.left)){
            return false
        }
        //比较当前节点与上一个节点
        if(prev!=null && prev.val>=root.val){
            return false
        }

        //记录当前节点，方便后面右子节点查询用
        prev = root
        if( !isValidBST3(root.right)){
            return false
        }

        return true
    }

}